//
//  InsertionSort.c
//  AlgorithmLearning
//
//  Created by aron on 2017/11/2.
//  Copyright © 2017年 aron. All rights reserved.
//

#include "InsertionSort.h"

void Insertionsort(ElementType arr[], int count) {
    int i;
    int j;
    for (i = 1; i < count; i++) {
        ElementType tmp = arr[i];
        // 把i位置的元素插入到前i个元素中
        // tmp < arr[j-1] 这个判断条件需要加在for循环的判断条件中，
        // 否则会出现j多减1的情况，导致排序出问题
        for (j = i; j > 0 && tmp < arr[j-1]; j--) {
            // 往后移动一个位置
            arr[j] = arr[j-1];
        }
        arr[j] = tmp;
    }
}

void Insertionsort1(ElementType arr[], int count) {
    int i; 
    int j;
    for (i = 1; i < count; i++) {
        ElementType tmp = arr[i];
        for (j = i; j > 0 && tmp < arr[j-1]; j--) {
            // 交换元素
            tmp = arr[j];
            arr[j] = arr[j-1];
            arr[j - 1] = tmp;
        }
    }
}

// 下面是错误的示例代码
void Insertionsort_bad1(ElementType arr[], int count) {
    int i;
    int j;
    for (i = 1; i < count; i++) {
        ElementType tmp = arr[i];
        // 把i位置的元素插入到前i个元素中
        _Bool isChanged = 0;
        for (j = i; j > 0; ) {
            // 往后移动一个位置
            if (tmp < arr[j-1]) {
                arr[j] = arr[j-1];
                isChanged = 1;
            }
            j--;
        }
        // 放到指定位置
        if (isChanged) {
            arr[j] = tmp;
        }
    }
}
